package com.dy.分类.二叉树._199二叉树的右视图;

import com.dy.树.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,3,null,5,null,4]
 * 输出: [1, 3, 4]
 * 解释:
 * <p>
 * 1            <---
 * /   \
 * 2     3         <---
 * \     \
 * 5     4       <---
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root==null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            TreeNode tmp = null;
            while (size > 0) {
                  tmp = q.poll();
                  size--;
                  if(tmp.left!=null) q.add(tmp.left);
                  if(tmp.right!=null) q.add(tmp.right);
            }
            res.add(tmp==null?null:tmp.val);
        }
        return res;
    }
}
